package zuochengyun;

import org.junit.Assert;

import java.util.*;
import java.util.Map.Entry;

//找出出现次数大于K的数
public class MoreThanKTimesNumber {

    private static final int MAX = 1000;

    Random random = new Random();

    public static void main(String[] args){
        MoreThanKTimesNumber object = new MoreThanKTimesNumber();
//        int[] array = new int[MAX];
//        HashSet<Integer> set = new HashSet<>(1 << 10);
//        for (int j = 0; j < 1000; j++) {
//            set.clear();
//            int length = object.random.nextInt(20) + MAX / 3 + 1;
//            int[] index = new int[length];
//            for (int i = 0; i < length; ) {
//                int cur = object.random.nextInt(MAX);
//                if(set.contains(cur)){
//                    continue;
//                }
//                set.add(cur);
//                index[i] = cur;
//                i++;
//            }
//            for (int i = 0; i < array.length; i++) {
//                array[i] = object.random.nextInt(1000);
//            }
//            int fixNum = object.random.nextInt(1000);
//            for (int i = 0; i < index.length; i++) {
//                array[index[i]] = fixNum;
//            }
//            int test = object.moreThanOneThirdNum(array);

        int[] array = {1, 3, 4, 4, 1, 3, 1, 0};
        int test = object.moreThanOneThirdNum(array);
            int[] res = object.moreThanOneThird_2(array);
            if (test != res[0] && test != res[1]){
                System.err.println("test" + Arrays.toString(array));
                System.out.println("length: " + "real " + res[0] + "   " +  res[1] + "  " + res[2] + "  " + test);
                return;
            }
//        }

//        int[] array = {332, 467, 797, 797, 595, 797, 673, 797, 758, 79, 797, 139, 400, 680, 797, 647, 797, 354,
//                797, 379, 616, 797, 295, 703, 797, 676, 619, 797, 193, 319, 797, 108, 642, 711, 129, 797, 797,
//                797, 444, 797, 340, 462, 400, 935, 720, 170, 472, 797, 719, 592};
//        object.moreThanOneThirdNum(array);
//        int[] res = object.moreThanOneThird_2(array);
//        System.out.println("length: " + "real " + res[0] + "   " +  res[1] + "  " + res[2]);

    }

	/**
	 * 找出数组中出现次数超过一半的数字
	 * 核心思想是每遇到两个不同的数，就删掉，最后剩下的一定是超过一半的数
	 */
	public int MoreThanHalfNum_Solution(int[] array) {
		if (array == null || array.length < 0) {
			return -1;
		}
		int times = 0;
		int result = 0;  //结果
		for (int i = 0; i < array.length; i++) {
		    //times等于0表示刚好消除了不同的数
            //比如 a, b, a, c这种就是刚好消除(a, a, b, c也是)
			if (times == 0) {  //如果次数为0，那么将result 置为 array[i] ，并将times设为1.
				result = array[i];
				times++;
			} else {
				if (array[i] == result) {  //如果与之前保存的结果相同，将times++
					times++;
				} else {
					times--;  //否则，减减
				}
			}
		}
		if (isMoreThanHalf(array, result)) {
			return result;
		} else {
			return 0;
		}

	}

    public int moreThanOneThirdNum(int[] array) {
        if (array == null || array.length < 0) {
            return -1;
        }
        int timesa = 0;
        int timesb = 0;
        int resulta = 0;  //结果
        int resultb = 0;  //结果
        for (int i = 0; i < array.length; i++) {
            //times等于0表示刚好消除了不同的数
            //比如 a, b, a, c这种就是刚好消除(a, a, b, c也是)
            //这个算法有漏洞，比如之前已有timesa = 1, resulta = 767, 此时array[i] = 767,应该是将timesa++
            //而d得到的结果是timesb = 1, resultb = 767.
//            if (timesa == 0) {  //如果次数为0，那么将result 置为 array[i] ，并将times设为1.
//                resulta = array[i];
//                timesa++;
//            } else if(timesb == 0){
//                resultb = array[i];
//                timesb++;
//            } else {
//                if (array[i] == resulta) {  //如果与之前保存的结果相同，将times++
//                    timesa++;
//                } else if (array[i] == resultb){
//                    timesb++;  //否则，减减
//                } else {
//                    timesa--;
//                    timesb--;
//                }
//            }
			//因为timesa等于0的时候是需要更新resulta的值的，所以这里判断不等于0
			//其实也可以array[i] == resulta || times == 0然后将注释解注释就行
            if(array[i] == resulta && timesa != 0){
                //resulta = array[i];
                timesa++;
            } else if(array[i] == resultb && timesb != 0){
                //resultb = array[i];
                timesb++;
            } else {
                if (timesa == 0) {
                    resulta = array[i];
                    timesa++;
                } else if (timesb == 0) {
                    resultb = array[i];
                    timesb++;
                } else {
                    timesa--;
                    timesb--;
                }
            }

        }
        int count = 0;
        //最后还需要判断到底是哪个大于1/3了
//		for (int i = 0; i < array.length; i++) {
//			if(array[i] == resulta){
//				count++;
//			}
//		}
		//之前我以为还需要判断谁是大于1 / 3的，其实不然，只需要知道谁的times大于等于2就行

		System.out.println("resulta: " + resulta + " resultb: " + resultb);
		System.out.println("timesa: " + timesa + " timesb: " + timesb);
        return timesa > 1 ? resulta : resultb;
    }

    public int[] moreThanOneThird_2(int[] array){
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[3];
        int index = 0;
        Integer temp;
        for (int i = 0; i < array.length; i++) {
            if((temp = map.get(array[i])) != null) {
                if(temp > array.length / 3 - 1){
                    result[index++] = array[i];
                    map.put(array[i], 0);
                } else {
                    map.put(array[i], temp + 1);
                }
            } else {
                map.put(array[i], 1);
            }
        }
        result[2] = index;
        return result;
    }

	// 判断是否超过了一半
	public boolean isMoreThanHalf(int[] array, int result) {
		int count = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == result) {
				count++;
			}
		}
		if (count > array.length / 2) {
			return true;
		}
		return false;
	}

	//核心思想就是一旦找到K个不同的数之后，就删除掉这些数，那么最后剩下的数就一定是大于K次的
	public void printKMajor(int[] arr, int K){
		if(K < 2){
			System.out.println("the value is invalid");
			return;
		}
		HashMap<Integer, Integer> candidates = new HashMap<>();
		for (int i = 0; i < arr.length; i++) {
			if(candidates.containsKey(arr[i])){
				candidates.put(arr[i], candidates.get(arr[i]) + 1);
			}else{
				//把所有不同的数减1
				if(candidates.size() == K - 1){
					allCandsMinusOne(candidates);
				}else{
					candidates.put(arr[i], 1);
				}
			}
		}
		
		HashMap<Integer, Integer> reals = getReals(arr, candidates);
		//用来判断是否可以打印
		boolean canPrint = false;
		for (Entry<Integer, Integer> set : candidates.entrySet()) {
			Integer key = set.getKey();
			if(reals.get(key) > arr.length / K){
				canPrint = true;
				System.out.println(key + " ");
			}
		}
		System.out.println(canPrint ? "" : "no such number");
	}
	
	/**
	 * 将所有的candidates减1
	 * @param candidates
	 */
	public void allCandsMinusOne(HashMap<Integer, Integer> candidates){
		//记录需要移除的key
		List<Integer> removeList = new LinkedList<>();
		for(Entry<Integer, Integer> set : candidates.entrySet()){
			Integer key = set.getKey();
			Integer value = set.getValue();
			if(value == 1){
				removeList.add(key);
			}
			candidates.put(key, value - 1);
		}
		
		for (Integer removeKey : removeList) {
			candidates.remove(removeKey);
		}
	}
	
	/**
	 * 得到candidates 中记录的最后剩下的数出现的次数，已验证是否出现了K次
	 * @param arr
	 * @param candidates
	 * @return
	 */
	public HashMap<Integer, Integer> getReals(int[] arr, HashMap<Integer, Integer> candidates){
		HashMap<Integer, Integer> reals = new HashMap<>();
		for (int i = 0; i < arr.length; i++) {
			int curNum = arr[i];
			if(candidates.containsKey(curNum)){
				if(reals.containsKey(curNum)){
					reals.put(curNum, reals.get(curNum) + 1);
				}else{
					reals.put(curNum, 1);
				}
			}
		}
		return reals;
	}
}
